package top.lyc829.leetcode.T146;

import java.util.*;

class LRUCache {

    class DLinkedList {
        int key;
        int value;
        DLinkedList pre;
        DLinkedList next;

        public DLinkedList() {
        }

        public DLinkedList(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;
    private int count = 0;

    private Map<Integer, DLinkedList> map = new HashMap<>();
    private DLinkedList mHead, mTail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        mHead = new DLinkedList();
        mTail = new DLinkedList();
        mHead.pre = null;
        mHead.next = mTail;
        mTail.pre = mHead;
        mTail.next = null;
    }

    public int get(int key) {

        if (!map.containsKey(key)) {
            return -1;
        } else {
            DLinkedList dLinkedList = map.get(key);
            moveToHead(dLinkedList);
            return dLinkedList.value;
        }

    }

    public void put(int key, int value) {

        if (!map.containsKey(key)) {
            DLinkedList dLinkedList = new DLinkedList(key, value);
            insertToHead(dLinkedList);
            map.put(key, dLinkedList);
            count++;
            if (count > capacity) {
                DLinkedList dLinkedList2 = deleteTail();
                map.remove(dLinkedList2.key);
                count--;
            }

        } else {
            DLinkedList dLinkedList = map.get(key);
            dLinkedList.value = value;
            moveToHead(dLinkedList);

        }
    }

    private void moveToHead(DLinkedList dLinkedList) {
        map.put(dLinkedList.key, dLinkedList);
        dLinkedList.pre.next = dLinkedList.next;
        dLinkedList.next.pre = dLinkedList.pre;
        insertToHead(dLinkedList);
    }

    private void insertToHead(DLinkedList dLinkedList) {
        dLinkedList.pre = mHead;
        dLinkedList.next = mHead.next;
        mHead.next.pre = dLinkedList;
        mHead.next = dLinkedList;
    }

    private DLinkedList deleteTail() {
        DLinkedList tail = mTail.pre;
        tail.pre.next = mTail;
        mTail.pre = tail.pre;
        return tail;
    }

    public static void main(String[] args) {
        LRUCache lRUCache = new LRUCache(2);
        lRUCache.put(1, 1); // 缓存是 {1=1}
        lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        lRUCache.get(1);    // 返回 1
        lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        lRUCache.get(2);    // 返回 -1 (未找到)
        lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        lRUCache.get(1);    // 返回 -1 (未找到)
        lRUCache.get(3);    // 返回 3
        lRUCache.get(4);    // 返回 4

    }

}

